package work.shuangzhizhen;

import java.lang.reflect.Array;
import java.util.*;

public class Problem15 {

    //SET去重，但是for太多超时
    public List<List<Integer>> threeSum(int[] nums) {
        Set<List<Integer>> set = new HashSet();
        for (int i = 0; i < nums.length - 2; i++) {
            for (int j = i + 1; j < nums.length - 1; j++)
                for (int k = j + 1; k < nums.length; k++) {
                    if (nums[i] + nums[j] + nums[k] == 0) {
                        List<Integer> list = new ArrayList<>();
                        int a[] = {nums[i], nums[j], nums[k]};
                        Arrays.sort(a);
                        for (int num : a) {
                            list.add(num);
                        }
                        set.add(list);
                    }
                }
        }
        List<List<Integer>> ans = new ArrayList<>();
        for (List<Integer> MY : set) {
            ans.add(MY);
        }
        return ans;
    }


    public List<List<Integer>> threeSum1(int[] nums) {
        List<List<Integer>> ans = new ArrayList<>();
        Arrays.sort(nums);
        for (int i = 0; i < nums.length - 2; i++) {
            if (nums[i] > 0) break; // 如果当前数字大于0，则三数之和一定大于0，所以结束循环
            if (i > 0 && nums[i] == nums[i - 1]) continue; // 去重
            int j = i + 1, k = nums.length - 1;
            while (j < k) {
                int sum = nums[i] + nums[j] + nums[k];
                if (sum == 0) {
                    List<Integer> list = new ArrayList<>();
                    list = Arrays.asList(nums[i], nums[j], nums[k]);
                    while (j < k && nums[j] == nums[j + 1]) j++;
                    while (j < k && nums[k] == nums[k - 1]) k--;
                    ans.add(list);
                    j++;
                    k--;
                } else if (sum > 0) {
                    k--;
                } else {
                    j++;
                }
            }
        }
        return ans;
    }


    public List<List<Integer>> threeSum12(int[] nums) {
        List<List<Integer>> ans = new ArrayList<>();
        Arrays.sort(nums);
        for (int i = 0; i < nums.length - 2; i++) {
            if (nums[i] > 0) break;
            if (i > 0 && nums[i] == nums[i - 1]) continue; // 去重
            int j = i + 1, k = nums.length - 1;
            while (j < k) {
                int sum = nums[i] + nums[j] + nums[k];
                if (sum == 0) {
                    List<Integer> list = Arrays.asList(nums[i], nums[j], nums[k]);
                    ans.add(list);
                    while (j < k && nums[k] == nums[k - 1]) {
                        k = k--;
                    }
                    while (j < k && nums[j] == nums[j + 1]) {
                        j = j++;
                    }
                    j++;
                    k--;
                } else if (sum > 0) {
                    k--;
                } else {
                    j++;
                }

            }
        }
        return ans;
    }

    public static void main(String[] args) {
        Problem15 problem15 = new Problem15();
        int a[] = {0, 0, 0, 0};
        List<List<Integer>> lists = problem15.threeSum12(a);
        System.out.println(lists);
    }


    public List<List<Integer>> threeSum123(int[] nums) {
        List<List<Integer>> ans = new ArrayList<>();
        Arrays.sort(nums);
        int n = nums.length - 1;
        for (int i = 0; i < n - 1; i++) {
            if (nums[i] > 0) break;
            if (i > 0 && nums[i] == nums[i - 1]) continue;
            if (nums[n] + nums[n - 1] + nums[n - 2] < 0) break;
            int head = i + 1, tail = n;
            while (head < tail) {
                int sum = nums[i] + nums[head] + nums[tail];
                if (sum < 0) {
                    head++;
                } else if (sum > 0) {
                    tail--;
                } else {
                    List<Integer> temp = new ArrayList<>();
                    temp = Arrays.asList(nums[i], nums[head], nums[tail]);
                    ans.add(temp);
                    for (head++; head < tail && nums[head] == nums[head - 1]; head++) ;
                    for (tail--; head < tail && nums[tail] == nums[tail + 1]; tail--) ;
                }
            }
        }
        return ans;
    }


}

